#pragma once
#include <iostream>
#include <vector>

#include <cassert>
#include <cstdlib>
#include <time.h>
enum
{
    ASC, // 升序
    DESC // 降序
};

namespace mySort
{
    class Sort
    {
    public:
        // 堆排序
        void HeapSort(std::vector<int> &array, int flag = ASC)
        {
            assert(!array.empty());

            // 1. 构建堆：
            // 大堆 -> 升序 小堆 -> 降序
            CreateHeap(array, flag);

            // 2. 使用堆顶元素删除，来实现排序
            for (int i = 1; i < array.size(); ++i)
            {
                Swap(array[0], array[array.size() - i]);
                Downward(array, 0, flag, array.size() - i);
            }
        }

        // 快速排序
        void qSort(std::vector<int> &array, int flag = ASC)
        {
            srand(time(nullptr));
            _qSort(array, 0, array.size() - 1, flag);
        }

        // 归并排序
        void mSort(std::vector<int>& array, int flag = ASC)
        {
            _mSort(array, 0, array.size() - 1, flag);
        }

        // 计数排序
        void cSort(std::vector<int>& array, int flag = ASC)
        {
            // 通过哈希映射来实现
            // 开辟一个新数组，数组的大小由原数组中最大元素决定
            // 原数组的值 映射到 新数组的对应数组下标中
            // 遍历新数组，复制到原数组中
        }

        // 打印
        void Print(const std::vector<int> &array)
        {
            for (const auto &e : array)
            {
                std::cout << e << " ";
            }
            std::cout << std::endl;
        }

    private:

        // 归并排序递归函数
        void _mSort(std::vector<int>& array, int begin, int end, int flag)
        {
            if(begin >= end) return;

            int tmp = begin + (end - begin) / 2; // 注意起始位置
            _mSort(array, begin, tmp, flag);
            _mSort(array, tmp + 1, end, flag);

            // 比较大小，排序
            int arr[end - begin + 1];
            int pos = 0;
            int i = begin, j = tmp + 1;

            while(i <= tmp && j <= end)
            {
                if(flag = ASC)
                {
                    if(array[i] < array[j]) arr[pos++] = array[i++];
                    else                    arr[pos++] = array[j++];
                }
                else
                {
                    if(array[i] > array[j]) arr[pos++] = array[i++];
                    else                    arr[pos++] = array[j++];
                }
                
            }
            
            while(i <= tmp) arr[pos++] = array[i++];
            while(j <= end) arr[pos++] = array[j++];

            for(int x = 0; x < end - begin + 1; ++x) array[x + begin] = arr[x];
        }   

        // 快速排序递归函数
        // [begin, left] < key 、 [left + 1, right - 1] == key 、 [right, end] > key
        void _qSort(std::vector<int> &array, int begin, int end, int flag)
        {
            if (begin >= end)
            {
                return;
            }
            int key = array[(rand() % (end - begin + 1)) + begin]; // 选择基准元素
            int left = begin - 1, right = end + 1;
            int cur = begin; // 开始遍历的位置

            while (cur < right)
            {
                if (flag == ASC)
                {
                    if (array[cur] < key)
                        Swap(array[++left], array[cur++]);
                    else if (array[cur] == key)
                        ++cur;
                    else
                        Swap(array[--right], array[cur]);
                }
                else
                {
                    if (array[cur] > key)
                        Swap(array[++left], array[cur++]);
                    else if (array[cur] == key)
                        ++cur;
                    else
                        Swap(array[--right], array[cur]);
                }
            }

            _qSort(array, begin, left, flag);
            _qSort(array, right, end, flag);
        }

        // 构建堆
        void CreateHeap(std::vector<int> &array, int flag)
        {
            int parent = array.size() / 2 - 1; // 最后一个非叶子结点
            // 向下调整
            while (parent >= 0)
            {
                Downward(array, parent, flag, array.size());
                --parent;
            }
        }

        // 向下调整（只从给定位置，向下调整一次）
        void Downward(std::vector<int> &array, int parent, int flag, int size)
        {
            while (parent <= size / 2 - 1) // 直到 到达最后一个非叶子结点
            {
                int lchild = parent * 2 + 1;
                int rchild = parent * 2 + 2;
                int child = 0;
                // 找孩子结点中较大/ 较小的一个
                if (lchild == size - 1)
                    child = lchild;
                else
                {
                    if (flag == DESC)
                        child = array[lchild] > array[rchild] ? rchild : lchild;
                    else
                        child = array[lchild] < array[rchild] ? rchild : lchild;
                }
                // 比较父亲与孩子的大小
                if (array[parent] > array[child])
                {
                    if (flag == DESC)
                        Swap(array[parent], array[child]);
                    else
                        break;
                }
                else
                {
                    if (flag == ASC)
                        Swap(array[parent], array[child]);
                    else
                        break;
                }
                parent = child;
            }
        }

        // 交换
        void Swap(int &a, int &b)
        {
            int tmp = a;
            a = b;
            b = tmp;
        }
    };

}